/* Mergesort. Recursively sort 2 subarrays 0..mid and mid+1..n and then merge
 * them */
#include <stdio.h>

void print_arr(int arr[], int n)
{
	int i = 0;

	for (i = 0; i < n; i++)
		printf("%4d ", arr[i]);

	printf("\n");
}


/* Merges an array which is of the type 2 sorted sub arrays. 0..mid and
 * mid+1..n */
void merge(int arr[], int n)
{
	int mid = n / 2;
	/* Lazy. TODO: Allocate by size */
	int merged[100];
	int i = 0, j = mid, k = 0;

	while(i < mid && j < n) {
		if(arr[i] < arr[j])
			merged[k++] = arr[i++];
		else
			merged[k++] = arr[j++];
	}

	while(i < mid)
		merged[k++] = arr[i++];

	while(j < n)
		merged[k++] = arr[j++];

	/* Copy the merged array onto the original array */
	i = 0;
	j = 0;
	while(i < n)
		arr[i++] = merged[j++];
	/*print_arr(merged,k);*/
}

void merge_sort(int arr[], int n)
{
	int merged[100];
	int i=0, j=0;

	int mid = n/2;

#if 1
	printf("Sorting array: ");
	print_arr(arr, n);
#endif

	if(n == 1)
		return;

	/* Recursively merge sort the two sub arrays */
	merge_sort(arr, mid);
	merge_sort(arr + mid, n - mid);

	/* Merge the 2 sorted sub arrays */
	merge(arr, n);

#if 1
	printf("Merged array: ");
	print_arr(arr, n);
#endif
}


int main(void)
{
	int arr[] = { 9, 22, 13, 43, 67, 7, 4, 15, 81, 46, 64, 8, 17, 18, 93 };
	int size = sizeof(arr)/sizeof(arr[0]);

	print_arr(arr, size);
	merge_sort(arr, size);
	print_arr(arr, size);

	return 0;
}






